Monotonic array [Two Pass,One Pass]

Time: O(N); Space: O(1); easy

An array is monotonic if it is either monotone increasing or monotone decreasing.

An array A is monotone increasing if for all i <= j, A[i] <= A[j]. An array A is monotone decreasing if for all i <= j, A[i] >= A[j].

Return true if and only if the given array A is monotonic.

Example 1:

Input: A = [1,2,2,3]

Output: True

Example 2:

Input: A = [6,5,4,4]

Output: True

Example 3:

Input: A = [1,3,2]

Output: False

Example 4:

Input: A = [1,2,4,5]

Output: True

Example 5:

Input: A = [1,1,1]

Output: True

Note:

• 1 <= A.length <= 50000

• -100000 <= A[i] <= 100000

1. Two Pass

Intuition An array is monotonic if it is monotone increasing, or monotone decreasing. Since a <= b and b <= c implies a <= c, we only need to check adjacent elements to determine if the array is monotone increasing (or decreasing, respectively). We can check each of these properties in one pass.

Algorithm To check whether an array A is monotone increasing, we’ll check A[i] <= A[i+1] for all i. The check for monotone decreasing is similar.

class Solution1(object):
    """
    Two Pass
    """
    def isMonotonic(self, A):
        """
        :type A: List[int]
        :rtype: bool
        """
        return (all(A[i] <= A[i+1] for i in range(len(A) - 1)) or
                all(A[i] >= A[i+1] for i in range(len(A) - 1)))

s = Solution1()
A = [1,2,2,3]
assert s.isMonotonic(A) == True
A = [6,5,4,4]
assert s.isMonotonic(A) == True
A = [1,3,2]
assert s.isMonotonic(A) == False
A = [1,2,4,5]
assert s.isMonotonic(A) == True
A = [1,1,1]
assert s.isMonotonic(A) == True

2. One Pass

Intuition To perform this check in one pass, we want to handle a stream of comparisons from {-1, 0, 1}, corresponding to <, ==, or >. For example, with the array [1, 2, 2, 3, 0], we will see the stream (-1, 0, -1, 1).

Algorithm Keep track of store, equal to the first non-zero comparison seen (if it exists.) If we see the opposite comparison, the answer is False. Otherwise, every comparison was (necessarily) in the set {-1, 0}, or every comparison was in the set {0, 1}, and therefore the array is monotonic.

class Solution2(object):
    """
    One Pass
    """
    def cmp(self, a, b):
        if a < b:
            return -1
        elif a > b:
            return 1
        else:
            return 0

    def isMonotonic(self, A):
        """
        :type A: List[int]
        :rtype: bool
        """
        store = 0
        for i in range(len(A) - 1):
            c = self.cmp(A[i], A[i+1])
            if c:
                if c != store != 0:
                    return False
                store = c
        return True

s = Solution2()
A = [1,2,2,3]
assert s.isMonotonic(A) == True
A = [6,5,4,4]
assert s.isMonotonic(A) == True
A = [1,3,2]
assert s.isMonotonic(A) == False
A = [1,2,4,5]
assert s.isMonotonic(A) == True
A = [1,1,1]
assert s.isMonotonic(A) == True

class Solution3(object):
    def isMonotonic(self, A):
        """
        :type A: List[int]
        :rtype: bool
        """
        inc, dec = False, False
        for i in range(len(A) - 1):
            if A[i] < A[i + 1]:
                inc = True
            elif A[i] > A[i + 1]:
                dec = True
        return not inc or not dec

s = Solution3()
A = [1,2,2,3]
assert s.isMonotonic(A) == True
A = [6,5,4,4]
assert s.isMonotonic(A) == True
A = [1,3,2]
assert s.isMonotonic(A) == False
A = [1,2,4,5]
assert s.isMonotonic(A) == True
A = [1,1,1]
assert s.isMonotonic(A) == True

See also:

https://leetcode.com/problems/monotonic-array

https://www.lintcode.com/problem/monotonic-array